#! /usr/bin/env python
# -*- coding: utf-8 -*-

# Description
# Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

# Have you met this question in a real interview?
# Example
# For s1 = "aabcc", s2 = "dbbca"

# When s3 = "aadbbcbcac", return true.
# When s3 = "aadbbbaccc", return false.
# Challenge
# O(n2) time or better

# For s1 = "aabcc", s2 = "dbbca"
# When s3 = "aadbbcbcac", return true.


class Solution:
    """
    @param s1: A string
    @param s2: A string
    @param s3: A string
    @return: Determine whether s3 is formed by interleaving of s1 and s2
    """
    def isInterleave(self, s1, s2, out):
        '''
        '''
        self.len1, self.len2, self.len_out = len(s1), len(s2), len(out)
        self.s1, self.s2, self.out = s1, s2, out

        if self.len1 + self.len2 != self.len_out:
            return False

        self._build_table()

        return self.trace_table[self.len1][self.len2]

    def _build_table(self):
        ''' s1 作为行, s2作为列'''
        # print('build')
        row = [False] * (self.len2 + 1)
        self.trace_table = [ list(row) for i in range(self.len1 + 1)]

        self.trace_table[0][0] = True
        for i in range(1, self.len2 + 1):
            if self.out[i-1] == self.s2[i-1] and self.trace_table[0][i-1]:
                self.trace_table[0][i] = True
        for i in range(1, self.len1 + 1):
            if self.out[i-1] == self.s1[i-1] and self.trace_table[i-1][0]:
                self.trace_table[i][0] = True

        for row in range(1, self.len1 + 1):
            for col in range(1, self.len2 + 1):
                self.trace_table[row][col] = self._is_grid_true(row, col)

    def _is_grid_true(self, r, c):
        if self.out[r+c-1] == self.s1[r-1] and self.trace_table[r-1][c]:
            # print('ret True', r, c)
            return True

        if self.out[r+c-1] == self.s2[c-1] and self.trace_table[r][c-1]:
            # print('ret True', r, c)
            return True

        # print('ret false', r, c)
        return False


def main():
    print("start main")

    s = Solution()
    v = s.isInterleave('a', 'aa', 'aab')
    print(v)

if __name__ == "__main__":
    main()
